package alogrithm;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/8/25 17:22
 */
public class AllPathSourceTarget {

    private List<List<Integer>> paths = new ArrayList<>();
    private Deque<Integer> path = new ArrayDeque<>();


    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        path.add(0);
        dfs(graph, 0, graph.length - 1);
        return paths;
    }

    private void dfs(int[][] graph, int x, int n) {
        if (x == n) {
            paths.add(new ArrayList<>(path));
        }
        for (int y : graph[x]) {
            path.offerLast(y);
            dfs(graph, y, n);
            path.pollLast();
        }
    }

    public static void main(String[] args) {
        int[][] a = new int[][]{{1, 2}, {3}, {3}, {}};
        final AllPathSourceTarget allPathSourceTarget = new AllPathSourceTarget();
        final List<List<Integer>> lists = allPathSourceTarget.allPathsSourceTarget(a);
        lists.stream().forEach(e -> System.out.println(e));
    }

}
